package exp4;

import chapter15.javaFoundations2nd.LinkedQueue;
import chapter16.ArrayIterator;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * Created by 蜡笔小新丶 on 2017/11/20.
 */
public class AdjacencyMatrix<T>{
    ArrayList<T> node;
    private int N=0;

    public boolean [][]matrix;

    public AdjacencyMatrix(){
        node = new ArrayList<>();
    }

    public boolean addNode(T point){
        boolean result = node.add(point);
        matrix = new boolean[node.size()][node.size()];
        return result;
    }

    public boolean removeNode(T point){
        int index = node.indexOf(point);
        boolean result = node.remove(point);
        become(index);
        return result;
    }

    public boolean addSide(T A,T B) throws Exception {
        int num1 = node.indexOf(A);
        int num2 = node.indexOf(B);
        boolean result = false;
        if(num1==-1||num2==-1){
            throw new Exception("找不到该结点！");
        }else {
            matrix[num1][num2] = true;
            matrix[num2][num1] = true;
            result = true;
        }
        return result;
    }

    public boolean removeSide(T A,T B) throws Exception {
        int num1 = node.indexOf(A);
        int num2 = node.indexOf(B);
        boolean result = false;
        if(matrix[num1][num2]&&matrix[num2][num1]){
            matrix[num1][num2]=false;
            matrix[num2][num1]=false;
            result = true;
        }else {
            throw new Exception("找不到该边！");
        }
        return result;
    }

    public boolean isEmpty(){
        return node.isEmpty();
    }

    public int Size(){
        int result=0;
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[i].length;j++){
                if (matrix[i][j]==true)
                    result++;
            }
        }
        return result;
    }

    private void initialize(){
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[i].length;j++){
                matrix[i][j] = false;
            }
        }
    }

    public ArrayList<T> iteratorBFS(int start) throws Exception {
        int currentVertex;
        int next = -1;
        LinkedQueue<Integer> traversalQueue = new LinkedQueue<Integer>();
        ArrayList<T> iter = new ArrayList<>();
        boolean[] visited = new boolean[node.size()];
        for (int i = 0; i < visited.length; i++)
            visited[i] = false;
            traversalQueue.enqueue(start);
            visited[start] = true;

            while (!traversalQueue.isEmpty()) {
                currentVertex = traversalQueue.dequeue();
                iter.add(node.get(currentVertex));
                for (int j = 0; j < visited.length; j++) {
                    if (matrix[currentVertex][j] && !visited[j]) {
                        traversalQueue.enqueue(j);
                        visited[j] = true;
                    }
                }
            }
        for (int i = 0; i < visited.length; i++) {
            if (visited[i] == false) {
                next = i;
                break;
            }
        }
        if(next!=-1)
            iter.add(node.get(next));
        return iter;
    }

    private void become(int index){
        boolean [][] m = new boolean[node.size()][node.size()];
        for(int i=0;i<matrix.length;i++){
            if(i!=index) {
                int F = 0;
                for (int j = 0; j < matrix[i].length; j++) {
                    if(j!=index) {
                        m[N][F] = matrix[i][j];
                        F++;
                    }
                }
                N++;
            }
        }
        matrix = new boolean[node.size()][node.size()];
        matrix = m;
    }
}
